package service;

public class ReverseListNode {


    public class ReverseList {

    }

    //构建长度为n的单向链表，并实现链表反转，要求时间复杂度n​
    class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public Node createLinkedList(Node head, int[] arr) {
        if (null == arr || arr.length <= 0) return null;
        head = new Node(arr[0]);
        Node cur = head;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new Node(arr[i]);
            cur = cur.next;
        }

        return head;
    }


    public Node reverseList(Node head) {
        return recurMethod(head, null);
    }

    private Node recurMethod(Node cur, Node pre) {
        if (null == cur) return pre;    //递归终止条件
        Node reversedList = recurMethod(cur.next, cur);
        cur.next = pre;
        return reversedList;
    }

    public void print(Node cur) {
        while (null != cur) {
            System.out.print(cur.value + " -> ");
            cur = cur.next;
        }
        System.out.println("");
    }

    public void run() {
        int[] arr = {1, 2, 3, 4};
        Node head = createLinkedList(null, arr);
        print(head);
        head = reverseList(head);
        print(head);
    }


    public static void main(String[] args) {
        ReverseListNode runner = new ReverseListNode();
        runner.run();
    }


}
